//********************************************************************
//  LinkedSet.java       Authors: Lewis/Chase
//
//  Represents a linked implementation of a set.
//********************************************************************

package jss2;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;

import jss2.exceptions.EmptySetException;

public class DoubleLinkedSet <T> implements SetADT <T> {

	private static Random	rand	= new Random ();

	private DoubleNode <T>	contents;

	private int				count;						// the current number of elements in the set  

	//-----------------------------------------------------------------
	//  Creates an empty set.
	//-----------------------------------------------------------------
	public DoubleLinkedSet () {

		this.count = 0;
		this.contents = null;
	}

	//-----------------------------------------------------------------
	//  Adds the specified element to the set if it's not already
	//  present.
	//-----------------------------------------------------------------
	public void add (final T element) {

		//if (!this.contains (element)) {
			final DoubleNode <T> node = new DoubleNode <T> (element);
			node.setNext (this.contents);
			node.setPrevious(node.getPrevious());
			this.contents = node;
			this.count++;
		//}
	}

	//-----------------------------------------------------------------
	//  Adds the contents of the parameter to this set.
	//-----------------------------------------------------------------
	public void addAll (final SetADT <T> set) {

		final Iterator <T> scan = set.iterator ();

		while (scan.hasNext ())
			this.add (scan.next ());
	}

	//-----------------------------------------------------------------
	//  Returns true if this set contains the specified target
	//  element.
	//-----------------------------------------------------------------
	public boolean contains (final T target) {

		boolean found = false;

		DoubleNode <T> current = this.contents;

		for (int look = 0; look < this.count && !found; look++)
			if (current.getElement ().equals (target))
				found = true;
			else
				current = current.getNext ();

		return found;
	}

	//-----------------------------------------------------------------
	//  Returns true if this set contains exactly the same elements
	//  as the parameter.
	//-----------------------------------------------------------------
	public boolean equals (final SetADT <T> set) {

		boolean result = false;
		final DoubleLinkedSet <T> temp1 = new DoubleLinkedSet <T> ();
		final DoubleLinkedSet <T> temp2 = new DoubleLinkedSet <T> ();
		T obj;

		if (this.size () == set.size ()) {
			temp1.addAll (this);
			temp2.addAll (set);

			final Iterator <T> scan = set.iterator ();

			while (scan.hasNext ()) {
				obj = scan.next ();
				if (temp1.contains (obj)) {
					temp1.remove (obj);
					temp2.remove (obj);
				}

			}
			result = temp1.isEmpty () && temp2.isEmpty ();
		}

		return result;
	}

	//-----------------------------------------------------------------
	//  Returns true if this set is empty and false otherwise. 
	//-----------------------------------------------------------------
	public boolean isEmpty () {

		return this.size () == 0;
	}

	//-----------------------------------------------------------------
	//  Returns an iterator for the elements currently in this set.
	//-----------------------------------------------------------------
	public Iterator <T> iterator () {

		return new DoubleLinkedIterator <T> (this.contents);
	}

	//-----------------------------------------------------------------
	//  Removes the specified element from the set and returns it.
	//  Throws an EmptySetException if the set is empty and a
	//  NoSuchElemetnException if the target is not in the set.
	//-----------------------------------------------------------------
	public T remove (final T target) throws EmptySetException,
			NoSuchElementException {

		boolean found = false;
		DoubleNode <T> current;
		T result = null;

		if (this.isEmpty ())
			throw new EmptySetException ();

		if (this.contents.getElement ().equals (target)) {
			result = this.contents.getElement ();
			this.contents = this.contents.getNext ();
		} else {
			current = this.contents.getNext ();
			current.setPrevious(this.contents);
			for (int look = 0; look < this.count && !found; look++)
				if (current.getElement ().equals (target))
					found = true;
				else {
					current = current.getPrevious();
					current = current.getNext ();
				}

			if (!found)
				throw new NoSuchElementException ();

			result = current.getElement ();
			current.setPrevious (current.getNext ());
		}

		this.count--;

		return result;
	}

	//-----------------------------------------------------------------
	//  Removes a random element from the set and returns it. Throws
	//  an EmptySetException if the set is empty.
	//-----------------------------------------------------------------
	public T removeRandom () throws EmptySetException {

		DoubleNode <T> current;
		T result = null;

		if (this.isEmpty ())
			throw new EmptySetException ();

		final int choice = DoubleLinkedSet.rand.nextInt (this.count) + 1;

		if (choice == 1) {
			result = this.contents.getElement ();
			this.contents = this.contents.getNext ();
		} else {
			current = this.contents;
			current.setPrevious(this.contents);
			for (int skip = 2; skip < choice; skip++)
				current.getPrevious ();
			current.getNext ();
			result = current.getElement ();
			current.setPrevious (current.getNext ());
		}

		this.count--;

		return result;
	}

	//-----------------------------------------------------------------
	//  Returns the number of elements currently in this set.
	//-----------------------------------------------------------------
	public int size () {

		return this.count;
	}

	//-----------------------------------------------------------------
	//  Returns a string representation of this set. 
	//-----------------------------------------------------------------
	@Override
	public String toString () {

		String result = "";

		DoubleNode <T> current = this.contents;

		while (current != null) {
			result += current.getElement ().toString () + "\n";
			current = current.getNext ();
		}

		return result;
	}

	//-----------------------------------------------------------------
	//  Returns a new set that is the union of this set and the
	//  parameter.
	//-----------------------------------------------------------------
	public SetADT <T> union (final SetADT <T> set) {

		final DoubleLinkedSet <T> both = new DoubleLinkedSet <T> ();

		DoubleNode <T> current = this.contents;

		while (current != null) {
			both.add (current.getElement ());
			current = current.getNext ();
		}

		final Iterator <T> scan = set.iterator ();
		while (scan.hasNext ())
			both.add (scan.next ());

		return both;
	}
}
